import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    //两个链表合并函数
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        //加一个表头
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //两个链表都要不为空
        while(list1 != null && list2 != null) {
            //取较小值的节点
            if(list1.val <= list2.val) {
                cur.next = list1;
                //只移动取值的指针
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //哪个链表还有剩，直接连在后面
        if(list1 != null) {
            cur.next = list1;
        } else {
            cur.next = list2;
        }
        //返回值去掉头结点
        return head.next;
    }

    // 划分合并区间函数
    ListNode divideMerge(ArrayList<ListNode> lists,int left,int right) {
        if(left > right)
            return null;
        else if (left == right)
            return lists.get(left);
        //从中间分成两段，再将合并好的两段合并
        int mid = (left + right) / 2;
        return Merge(divideMerge(lists,left,mid),divideMerge(lists,mid + 1,right));
    }
        
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        return divideMerge(lists,0,lists.size()-1);
    }
}